|
In theoretical computer science and formal language theory, a regular language (also called a rational language〔〔) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science (as opposed to many regular expressions engines provided by modern programming languages, which are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression). Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem. In the Chomsky hierarchy, regular languages are defined to be the languages that are generated by Type-3 grammars (regular grammars). Regular languages are very useful in input parsing and programming language design. ==Formal definition== The collection of regular languages over an alphabet Σ is defined recursively as follows: * The empty language Ø is a regular language. * For each ''a'' ∈ Σ (''a'' belongs to Σ), the singleton language is a regular language. * If ''A'' and ''B'' are regular languages, then ''A'' ∪ ''B'' (union), ''A'' • ''B'' (concatenation), and ''A'' * (Kleene star) are regular languages. * No other languages over Σ are regular. See regular expression for its syntax and semantics. Note that the above cases are in effect the defining rules of regular expression. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Regular language」の詳細全文を読む スポンサード リンク
|